package com.mengfou.recursion;

import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

/**
 * @author mengfou
 */
public class Recursion {

    public static void main(String[] args) {
        int[] arr = new int[]{2, 3, 1, 5, 6, 3, 2, 7, 9};
        int maximumByRecursion = new Recursion().getMaximumByRecursion(arr);
        System.out.println(maximumByRecursion);
    }

    /**
     * 递归的完成字符串的翻转
     * @param str 待翻转字符串
     * @return 翻转后字符串
     */
    public String reverse(String str){
        int len = str.length();
        if(len <= 1){ // 长度为空或者为1均返回这个字符本身
            return str;
        }
        String left = str.substring(0, len / 2);
        String right = str.substring(len / 2, len);
        return reverse(right) + reverse(left);
    }

    /**
     * 二路归并排序
     * @param arr 待排序数组
     */
    public void twoWayMergeSort(int[] arr) {
        twoWaymergeSort(arr, 0, arr.length - 1);
    }

    private void twoWaymergeSort(int[] arr, int low, int high) {
        if(low < high){
            int mid = (low + high) / 2;
            twoWaymergeSort(arr, low, mid);
            twoWaymergeSort(arr, mid+1, high);
            merge(arr, low, mid, high);
        }
    }

    private void merge(int[] arr, int low, int mid, int high) {
        int[] temp = new int[high -low + 1];
        int index = 0;
        int p = low, q = mid + 1;
        while(p <= mid && q <= high){
            if(arr[p] > arr[q]){
                temp[index++] = arr[q++];
            }else{
                temp[index++] = arr[p++];
            }
        }
        while(p <= mid){
            temp[index++] = arr[p++];
        }
        while(q <= high){
            temp[index++] = arr[q++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[low + i] = temp[i];
        }
    }

    /**
     * 递归的查找数组中的最大值
     * @param arr 待查找数组
     * @return 最大值
     */
    public int getMaximumByRecursion(int[] arr){
        if(arr == null || arr.length == 0) return -1;
        return getMaximumValue(arr, 0, arr.length - 1);
    }

    private int getMaximumValue(int[] arr, int left, int right) {
        if(left == right) return arr[left];
        int mid = left + ((right - left) >> 1);
        int leftMaxValue = getMaximumValue(arr, left, mid);
        int rightMaxValue = getMaximumValue(arr, mid + 1, right);
        return Math.max(leftMaxValue, rightMaxValue);
    }


    /**
     * 使用递归来逆序一个栈
     * @param stack 待逆序栈
     * @return 逆序后的栈
     */
    public Stack<Integer> reverse(Stack<Integer> stack){
        if(stack.isEmpty()){
            return stack;
        }
        int last = getAndRemoveLastElement(stack); // 取得当前栈底元素
        reverse(stack);
        stack.push(last);
        return stack;
    }

    public int getAndRemoveLastElement(Stack<Integer> stack){
        int result = stack.pop();
        if(stack.isEmpty()){
            return result;
        }else{
            int last = getAndRemoveLastElement(stack); //递归到找到最后一个元素，命名为last
            stack.push(result);   //其他名称仍叫result，要重新压入栈
            return last;     //只返回last一个元素
        }
    }

    /**
     * 使用一个栈来实现另一个栈的排序
     * 2021-12-30
     * @param stack 待排序栈
     */
    public void sortStackByStack(Stack<Integer> stack){
        Stack<Integer> help = new Stack<Integer>();
        while(!stack.isEmpty()){
            int cur = stack.pop();
            while(!help.isEmpty() && cur > help.peek()){
                stack.push(help.pop());
            }
            help.push(cur);
        }
        while(!help.isEmpty()){
            stack.push(help.pop());
        }
    }

    /**
     * 汉诺塔，需要将A上的圆盘移动到C上，遵循以下规则：
     *  - 每次只能移动一个盘
     *  - 只能顶端操作
     *  - 盘子只能叠在比它大的盘子上
     * @param A 源
     * @param B 辅助空间
     * @param C 目标
     */
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C){
        int size = A.size(); // 多少个盘子
        // 定义递归函数move，表示将n个盘子通过辅组空间B移动到C
        move(size, A, B, C);
    }

    private void move(int size, List<Integer> a, List<Integer> b, List<Integer> c) {
        // 如果size == 1，那么直接将盘子移动到C即可
        if(size == 1){
            int remove = a.remove(a.size() - 1); // a.size() - 1 即表示最后的一个元素
            c.add(remove);
        } else{
            // 移动size-1个到B盘子, , 通过c
            move(size -1, a, c, b);
            // 移动1个到c盘子, 通过b
            move(1, a, b, c);
            // 将size - 1个盘子从b移动到c, 通过a
            move(size - 1, b, a, c);
        }
    }



}
